class Solution
{
public:
    int minimumTime(int n, vector<vector<int>> &relations, vector<int> &time)
    {
        vector<int> inDegrees(n + 1, 0);
        vector<vector<int>> outEdges(n + 1);
        for (auto &relation : relations)
        {
            outEdges[relation[0]].push_back(relation[1]);
            ++inDegrees[relation[1]];
        }
        unordered_map<int, int> prevLatestEndTime;
        unordered_map<int, int> courseEndTime;
        int allEndTime = 0;
        queue<int> q;
        for (int i = 1; i <= n; ++i)
        {
            if (inDegrees[i] == 0)
            {
                q.push(i);
                courseEndTime[i] = time[i - 1];
                allEndTime = max(allEndTime, time[i - 1]);
            }
        }
        while (!q.empty())
        {
            int course = q.front();
            q.pop();
            for (int nextCourse : outEdges[course])
            {
                prevLatestEndTime[nextCourse] = max(prevLatestEndTime[nextCourse], courseEndTime[course]);
                --inDegrees[nextCourse];
                if (inDegrees[nextCourse] == 0)
                {
                    q.push(nextCourse);
                    courseEndTime[nextCourse] = prevLatestEndTime[nextCourse] + time[nextCourse - 1];
                    allEndTime = max(allEndTime, courseEndTime[nextCourse]);
                }
            }
        }
        return allEndTime;
    }
};